package top.retain;

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * @author ivorfan
 * @date 2021/8/26 16:43
 */
public class SubarraySum {

    public static void main(String[] args) {
//        subarraySum(new int[]{1, 2, 3, 4, 5, 6}, 10);
        maxSlidingWindow(new int[]{1,3,-1,-3,5,3,6,7},3);
    }

    public static int subarraySum(int[] nums, int k) {
        if (nums == null)
            return 0;
        int count = 0;
        int n = nums.length;
        Map<Integer, Integer> map = new HashMap<>();
        //细节，这里需要预存前缀和为 0 的情况，会漏掉前几位就满足的情况
        //例如输入[1,1,0]，k = 2 如果没有这行代码，则会返回0,漏掉了1+1=2，和1+1+0=2的情况
        //输入：[3,1,1,0] k = 2时则不会漏掉
        //因为presum[3] - presum[0]表示前面 3 位的和，所以需要map.put(0,1),垫下底
        map.put(0, 1);
        int sum = 0;
        for (int num : nums) {
            sum += num;
            if (map.containsKey(sum - k)) {
                count += map.get(sum - k);
            }
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        return count;
    }

    public static int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        if (n == 1 || k == 1)
            return nums;
        // int[0] : num, int[1]:idx 先按num降序排列，然后按照idx降序排列
        PriorityQueue<int[]> queue = new PriorityQueue<>((o1, o2) ->
                o2[0] != o1[0] ? o2[0] - o1[0] : o2[1] - o1[1]);
        int[] res = new int[n - k + 1];
        // 初始化前k个数入堆
        for (int i = 0; i < k; i++) {
            queue.offer(new int[]{nums[i], i});
        }
        res[0] = queue.peek()[0];
        // 依次入堆
        for (int i = 1; i < n - k + 1; i++) {
            queue.offer(new int[]{nums[i + k - 1], i + k - 1});
            // 移除掉不属于窗口中的
            while (!queue.isEmpty() && queue.peek()[1] < i) {
                queue.poll();
                // System.out.println("i = "+ i +"时移除掉" +queue.poll()[0]);
            }
            // 剩下的就是属于窗口中最大的一个元素。注意不能是poll（）
            res[i] = queue.peek()[0];
        }
        return res;
    }
}
